package niuke.week02;

import java.util.Scanner;

/**
 1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
 2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。
                                    如果是非负数，代表此处有血瓶，能让骑士回血。
 3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?
 根据map,输出初始血量。
 */
public class QiShi {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int [][]arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        int [][]dp = new int[m][n];//从arr[i][j]到右下角最少需要多少初始血量

        dp[m-1][n-1] = arr[m-1][n-1]<0? Math.abs(arr[m-1][n-1])+1 : 1;

        for (int i = n-2; i >=0 ; i--) {//初始化最后一行
           dp[m-1][i] = Math.max(dp[m-1][i+1]-arr[m-1][i],1);
        }

        for (int i = m-2; i >=0 ; i--) {//初始化最后一列
            dp[i][n-1] = Math.max(dp[i+1][n-1]-arr[i][n-1],1);
        }

        for (int i = m-2; i >=0 ; i--) {
            for (int j = n-2; j >=0 ; j--) {
                int runRight = dp[i][j+1]-arr[i][j];
                int runDown = dp[i+1][j]-arr[i][j];
                dp[i][j] = Math.max( Math.min(runDown,runRight),1);
            }
        }


//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(dp[i][j]+"\t");
//            }
//            System.out.println();
//
//        }

        System.out.println(dp[0][0]);

    }
}